#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: mergen_links.py 
@version:
@time: 2024/01/23 
"""
from code.learn_algorithm_idea.double_points.cycle import ListNode

"""
Links = [
1-2-4,
2-4，
3-4-5，
]
"""
t0 = ListNode(1)
t1 = ListNode(2)
t2 = ListNode(4)
t3 = ListNode(2)
t4 = ListNode(4)
t5 = ListNode(3)
t6 = ListNode(4)
t7 = ListNode(4)

# 1
t0.next = t1
t1.next = t2
# 2
t3.next = t4
# 3
t5.next = t6
t6.next = t7

inputs = [t0, t3, t5]


def merge2link(head1, head2):
    point = mergedhead = ListNode(0)
    while head1 and head2:
        if head1.value <= head2.value:
            point.next = head1
            head1 = head1.next
        else:
            point.next = head2
            head2 = head2.next
        point = point.next
    if not head1:
        point.next = head2
    else:
        point.next = head1
    return mergedhead.next


def mergen_links(links):
    length = len(links)
    iterval = 1
    while length > iterval:
        for i in range(0, length - iterval, iterval * 2):
            links[i] = merge2link(links[i], links[i + iterval])
        iterval *= 2
    return links[0] if length > 0 else None


"""
我们将n个链表两两合并，最终合并成一个链表。

1 2 3 4 5 6 7 8
| | | | | | | |
 -   -   -   -
 
1-2 3-4 5-6 7-8
|   |   |   |
 ---     ---

1-2-3-4 5-6-7-8
|       |
--------

1-2-3-4-5-6-7-8

"""
if __name__ == '__main__':
    res = mergen_links(inputs)
    print(res.value)
    print(res.next.value)
    print(res.next.next.value)
